package com.example.demo.collections;

/**
 * 双向链表，适用于插入删除操作较多的场景，因为双向链表删除和插入的操作比较快，查询比较慢
 * 
 * @param <E>
 */
public class MyArrayLinkedList<E> {

	/**
	 * 头部
	 */
	private Node<E> first;
	/**
	 * 尾部
	 */
	private Node<E> last;
	private int size;

	public MyArrayLinkedList() {
		size = 0;
	}

	/**
	 * 插入到头部
	 * 
	 * @param e
	 */
	private void linkFirst(E e) {
		Node<E> f = first;
		Node<E> n = new Node<E>(e, null, f);
		first = n;
		if (f == null) {
			last = n;
		} else {
			f.prev = first;
		}
	}

	/**
	 * 插入到尾部
	 * 
	 * @param e
	 */
	private void linkLast(E e) {
		Node<E> l = last;
		Node<E> n = new Node<E>(e, l, null);
		last = n;
		if (l == null) {
			first = n;
		} else
			l.next = last;
	}

	/**
	 * 删除头部
	 */
	private void unLinkFirst() {
		Node<E> next = first.next;
		Node<E> f = first;
		first = next;
		f.next = null;
		next.prev = null;
	}

	private void unLinkLast() {
		Node<E> prev = last.prev;
		Node<E> l = last;
		last = prev;
		l.prev = null;
		last.next = null;
	}

	private void unLink(Node<E> node) {
		if (node == null)
			return;
		if (node == first) {
			unLinkFirst();
		} else if (node == last) {
			unLinkLast();
		} else {
			Node<E> prev = node.prev;
			Node<E> next = node.next;
			prev.next = next;
			next.prev = prev;
		}
		node.prev = null;
		node.next = null;
		size--;
	}

	public boolean add(E e) {
		return addLast(e);
	}

	public boolean addLast(E e) {
		linkLast(e);
		size++;
		return true;
	}

	public boolean addFirst(E e) {
		linkFirst(e);
		size++;
		return true;
	}

	private Node<E> getNode(int index) {
		if (index < 0 || index > size)
			throw new IndexOutOfBoundsException("" + index);
		int mid = index >> 1;
		if (index > mid) {
			Node<E> n = last;
			for (int i = size - 1; i > index; i--)
				n = n.prev;
			return n;
		} else {
			Node<E> n = first;
			for (int i = 0; i < index; i++)
				n = n.next;
			return n;
		}
	}

	private Node<E> getNode(E e) {
		Node<E> f = this.first;
		while (f != null) {
			if (f.data == e || f.data.equals(e))
				return f;
			f = f.next;
		}
		return null;
	}

	public E get(E e) {
		Node<E> node = getNode(e);
		return node == null ? null : (E) node.data;
	}

	public E getFirst() {
		Node<E> f = first;
		return f == null ? null : (E) f.data;
	}

	public E getLast() {
		Node<E> l = last;
		return l == null ? null : (E) l.data;
	}

	public E get(int index) {
		Node<E> node = getNode(index);
		return node == null ? null : (E) node.data;
	}

	public E remove(E e) {
		Node<E> node = getNode(e);
		unLink(node);
		return node == null ? null : (E) node.data;
	}

	public E removeFirst() {
		Node<E> f = this.first;
		if (f == null)
			return null;
		unLinkFirst();
		return f.data;
	}

	public E removeLast() {
		Node<E> l = this.last;
		if (l == null)
			return null;
		unLinkLast();
		return l.data;
	}

	static class Node<E> {
		E data;
		Node<E> prev;
		Node<E> next;

		public Node(E data, Node<E> prev, Node<E> next) {
			this.data = data;
			this.prev = prev;
			this.next = next;
		}
	}

	@Override
	public String toString() {
		StringBuilder builder = new StringBuilder();
		if (first == null)
			return "[]";
		builder.append("[");
		Node<E> f = first;
		while (f != null) {
			builder.append(f.data);
			builder.append(", ");
			f = f.next;
		}
		return builder.substring(0, builder.length() - 2) + "]";
	}
}
